﻿#include <iostream>
#include <bits/stdc++.h>
using namespace std;

typedef char ElemType;

struct TreeNode {
    char data;
    vector<TreeNode*> children;
    TreeNode(char val) : data(val) {}
};

typedef TreeNode* Tree;

struct BiNode {
    ElemType data;
    BiNode* lchild, * rchild;
    BiNode(char val) : data(val), lchild(NULL), rchild(NULL) {}
};

typedef BiNode* BiTree;

void CreateTree(Tree& T, ifstream& inFile) {
    char ch;
    inFile >> ch;
    if (ch == '#') {
        T = NULL;
    }
    else {
        T = new TreeNode(ch);
        int childNum;
        inFile >> childNum;
        for (int i = 0; i < childNum; ++i) {
            Tree child;
            CreateTree(child, inFile);
            if (child != NULL) {
                T->children.push_back(child);
            }
        }
    }
}

BiTree TreeToBiTree(Tree treeRoot) {
    if (!treeRoot) return NULL;
    BiTree binaryRoot = new BiNode(treeRoot->data);
    if (!treeRoot->children.empty()) {
        binaryRoot->lchild = TreeToBiTree(treeRoot->children[0]);
        BiTree prev = binaryRoot->lchild;
        for (size_t i = 1; i < treeRoot->children.size(); ++i) {
            prev->rchild = TreeToBiTree(treeRoot->children[i]);
            prev = prev->rchild;
        }
    }
    return binaryRoot;
}

Tree BiTreeToTree(BiTree T) {
    if (!T) return NULL;
    Tree root = new TreeNode(T->data);
    Tree lastChild = NULL;
    if (T->lchild) {
        lastChild = BiTreeToTree(T->lchild);
        root->children.push_back(lastChild);
    }
    BiTree cur = T->rchild;
    while (cur) {
        if (!lastChild) {
            lastChild = new TreeNode(cur->data);
            root->children.push_back(lastChild);
        }
        else {
            lastChild->children.push_back(BiTreeToTree(cur));
            lastChild = lastChild->children.back();
        }
        cur = cur->rchild;
    }
    return root;
}

void LevelOrderTraversal(BiTree T) {
    if (!T) return;
    queue<BiNode*> q;
    q.push(T);
    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; ++i) {
            BiNode* node = q.front();
            q.pop();
            cout << node->data;
            if (node->lchild) q.push(node->lchild);
            if (node->rchild) q.push(node->rchild);
        }
    }
}

void PreOrder(BiTree T) {
    if (T) {
        cout << T->data;
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}

void PostOrder(BiTree T) {
    if (T) {
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        cout << T->data;
    }
}

void PreOrderBiTreeNonRecursive(BiTree T) {
    if (!T) return;
    stack<BiNode*> s;
    s.push(T);
    while (!s.empty()) {
        BiNode* node = s.top();
        s.pop();
        cout << node->data << ' ';
        if (node->rchild) s.push(node->rchild);
        if (node->lchild) s.push(node->lchild);
    }
}

void PostOrderBiTreeNonRecursive(BiTree T) {
    if (!T) return;
    stack<BiNode*> s1, s2;
    s1.push(T);
    while (!s1.empty()) {
        BiNode* node = s1.top();
        s1.pop();
        s2.push(node);
        if (node->lchild) s1.push(node->lchild);
        if (node->rchild) s1.push(node->rchild);
    }
    while (!s2.empty()) {
        BiNode* node = s2.top();
        s2.pop();
        cout << node->data << ' ';
    }
}

int main() {
    Tree treeRoot0;
    ifstream inFile("input.txt");
    if (!inFile.is_open()) {
        cerr << "无法打开文件 input.txt" << endl;
        return 1;
    }

    CreateTree(treeRoot0, inFile);
    inFile.close();

    BiTree biTreeRoot = TreeToBiTree(treeRoot0);
    Tree treeRoot = BiTreeToTree(biTreeRoot);
    cout << "树的层次非递归遍历";
    LevelOrderTraversal(biTreeRoot);
    cout << endl;

    cout << "树的前序递归遍历";
    PreOrder(biTreeRoot);
    cout << endl;

    cout << "树的后序递归遍历";
    PostOrder(biTreeRoot);
    cout << endl;

    cout << "二叉树的前序非递归遍历: ";
    PreOrderBiTreeNonRecursive(biTreeRoot);
    cout << endl;

    cout << "二叉树的后序非递归遍历: ";
    PostOrderBiTreeNonRecursive(biTreeRoot);
    cout << endl;

    cout << "2023211438 刘冰";

    return 0;
}